package j2025.j02;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * @Author 猫大仙
 */
public class j0209 {
    /**
     * 127. 单词接龙
     * 字典 wordList 中从单词 beginWord 到 endWord 的 转换序列 是一个按下述规格形成的序列 beginWord -> s1 -> s2 -> ... -> sk：
     *
     * 每一对相邻的单词只差一个字母。
     *  对于 1 <= i <= k 时，每个 si 都在 wordList 中。注意， beginWord 不需要在 wordList 中。
     * sk == endWord
     * 给你两个单词 beginWord 和 endWord 和一个字典 wordList ，
     * 返回 从 beginWord 到 endWord 的 最短转换序列 中的 单词数目 。如果不存在这样的转换序列，返回 0 。
     * @param beginWord
     * @param endWord
     * @param wordList
     * @return
     */
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        char[] str = new char[26];
        for (int i = 0; i < 26; i++) {
            str[i] = (char)('a'+i);
        }
        //是否转换过
        HashSet<String> vis = new HashSet<>();
        //wordList
        HashSet<String> set = new HashSet<>();
        for(String s:wordList){
            set.add(s);
        }
        if(beginWord.equals(endWord)){
            return 1;
        }
        if(!set.contains(endWord)){
            return 0;
        }
        Queue<String> q = new LinkedList<>();
        q.add(beginWord);
        vis.add(beginWord);
        int ret = 1;
        while(!q.isEmpty()){
            ret++;
            int sz = q.size();
            while(sz--!=0){
                String ss = q.poll();
                for (int i = 0; i < ss.length(); i++) {
                    char[] s = ss.toCharArray();
                    for (int j = 0; j < 26; j++) {
                        s[i] = str[j];
                        String tmp = new String(s);
                        if(set.contains(tmp) && !vis.contains(tmp)){
                            if(tmp.equals(endWord)){
                                return ret;
                            }
                            vis.add(tmp);
                            q.add(tmp);
                        }
                    }
                }
            }
        }
        return 0;
    }
}
